package algorithm;



public class FloydWarshall {
	int countV;
	int countE;
	int [][][]A;
	final static int MAX = 0x7FFFFFFF;
	
	public void InitData(){
		DataReader reader = new DataReader();
		reader.SetFilename("C:\\tmp\\edges.txt");
		
		String str;
		str = reader.GetNextLine();
		String[] parser = str.split(" ");
		countV = Integer.parseInt(parser[0]);
		countE = Integer.parseInt(parser[1]);
		A = new int[2][countV][countV];
		
		for(int i = 0; i < countV; i++)
		{
			for(int j = 0; j < countV; j++){
				if(i == j)
					A[0][i][j] = 0;
				else
					A[0][i][j] = MAX;
			}
		}
		
		while((str = reader.GetNextLine()) != null)
		{
			parser = str.split(" ");
			int tail = Integer.parseInt(parser[0]) - 1;
			int head = Integer.parseInt(parser[1]) - 1;
			int weight = Integer.parseInt(parser[2]);
			A[0][tail][head] = weight;
		}
	
	}

	int GetMinValue(int i, int j, int k, int last[][]){
		int min = last[i][j];
		
		if(last[i][k] < MAX && last[k][j] < MAX && min > last[i][k] + last[k][j]){
			min = last[i][k] + last[k][j];
		}
		
		return min;
	}
	
	
	public void RunFloydWarshall(){
		int last[][] = A[0];
		int cur[][] = A[1];
		
		for(int k = 1; k <= countV; k++)
		{
			for(int i = 0; i < countV; i++){
				for(int j = 0; j < countV; j++){
					cur[i][j] = GetMinValue(i, j, k - 1, last);
				}
			}
			int temp[][] = last;
			last = cur;
			cur = temp;
		}
		
		int temp[][] = last;
		last = cur;
		cur = temp;
		
		
		int min = MAX;
		
		for(int i = 0; i < countV; i++){
			for(int j = 0; j < countV; j++){
				if(min > cur[i][j])
					min = cur[i][j];
			}
		}
		
		System.out.println("the shortest path among all pairs past is " + min);
	}
	
	
	public void PrintData(int cur[][]){
		for(int i = 0; i < countV; i++){
			for(int j = 0; j < countV; j++){
				System.out.print(cur[i][j] + "\t");
			}
			System.out.println("\n");
		}
	}
}
